/*
 * Copyright 2010-2012 Susanta Tewari. <freecode4susant@users.sourceforge.net>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package bd.org.apache.commons.math.distribution;

import bd.org.apache.commons.math.exception.MathInternalError;
import bd.org.apache.commons.math.exception.NotStrictlyPositiveException;
import bd.org.apache.commons.math.exception.NumberIsTooLargeException;
import bd.org.apache.commons.math.exception.OutOfRangeException;
import bd.org.apache.commons.math.exception.util.LocalizedFormats;
import bd.org.apache.commons.math.random.RandomDataImpl;
import bd.org.apache.commons.math.util.FastMath;

import java.io.Serializable;

/**
 * Base class for integer-valued discrete distributions.  Default
 * implementations are provided for some of the methods that do not vary
 * from distribution to distribution.
 *
 * @version $Id: AbstractIntegerDistribution.java 1244107 2012-02-14 16:17:55Z erans $
 */
public abstract class AbstractIntegerDistribution implements IntegerDistribution, Serializable {

    /**
     * Serializable version identifier
     */
    private static final long serialVersionUID = -1146319659338487221L;

    /**
     * RandomData instance used to generate samples from the distribution.
     */
    protected final RandomDataImpl randomData = new RandomDataImpl();

    /**
     * Default constructor.
     */
    protected AbstractIntegerDistribution() {}

    /**
     * {@inheritDoc}
     * The default implementation uses the identity
     * <p>{@code P(x0 < X <= x1) = P(X <= x1) - P(X <= x0)}</p>
     */
    @Override
    public double cumulativeProbability(int x0, int x1) throws NumberIsTooLargeException {

        if (x1 < x0) {

            throw new NumberIsTooLargeException(
                LocalizedFormats.LOWER_ENDPOINT_ABOVE_UPPER_ENDPOINT, x0, x1, true);
        }

        return cumulativeProbability(x1) - cumulativeProbability(x0);
    }


    /**
     * {@inheritDoc}
     * The default implementation returns
     * <ul>
     * <li>{@link #getSupportLowerBound()} for {@code p = 0},</li>
     * <li>{@link #getSupportUpperBound()} for {@code p = 1}, and</li>
     * <li>{@link #solveInverseCumulativeProbability(double, int, int)} for
     * {@code 0 < p < 1}.</li>
     * </ul>
     */
    @Override
    public int inverseCumulativeProbability(final double p) throws OutOfRangeException {

        if ((p < 0.0) || (p > 1.0)) {
            throw new OutOfRangeException(p, 0, 1);
        }

        int lower = getSupportLowerBound();

        if (p == 0.0) {
            return lower;
        }

        if (lower == Integer.MIN_VALUE) {

            if (checkedCumulativeProbability(lower) >= p) {
                return lower;
            }

        } else {

            lower -= 1;    // this ensures cumulativeProbability(lower) < p, which

            // is important for the solving step
        }

        int upper = getSupportUpperBound();

        if (p == 1.0) {
            return upper;
        }

        // use the one-sided Chebyshev inequality to narrow the bracket
        // cf. AbstractRealDistribution.inverseCumulativeProbability(double)
        final double  mu               = getNumericalMean();
        final double  sigma            = FastMath.sqrt(getNumericalVariance());
        final boolean chebyshevApplies = !(Double.isInfinite(mu) || Double.isNaN(mu)
                                           || Double.isInfinite(sigma) || Double.isNaN(sigma)
                                           || (sigma == 0.0));

        if (chebyshevApplies) {

            double k   = FastMath.sqrt((1.0 - p) / p);
            double tmp = mu - k * sigma;

            if (tmp > lower) {
                lower = ((int) Math.ceil(tmp)) - 1;
            }

            k   = 1.0 / k;
            tmp = mu + k * sigma;

            if (tmp < upper) {
                upper = ((int) Math.ceil(tmp)) - 1;
            }
        }

        return solveInverseCumulativeProbability(p, lower, upper);
    }


    /**
     * This is a utility function used by {@link
     * #inverseCumulativeProbability(double)}. It assumes {@code 0 < p < 1} and
     * that the inverse cumulative probability lies in the bracket {@code
     * (lower, upper]}. The implementation does simple bisection to find the
     * smallest {@code p}-quantile <code>inf{x in Z | P(X<=x) >= p}</code>.
     *
     * @param p the cumulative probability
     * @param lower a value satisfying {@code cumulativeProbability(lower) < p}
     * @param upper a value satisfying {@code p <= cumulativeProbability(upper)}
     * @return the smallest {@code p}-quantile of this distribution
     */
    protected int solveInverseCumulativeProbability(final double p, int lower, int upper) {

        while (lower + 1 < upper) {

            int xm = (lower + upper) / 2;

            if ((xm < lower) || (xm > upper)) {

                /*
                 * Overflow.
                 * There will never be an overflow in both calculation methods
                 * for xm at the same time
                 */
                xm = lower + (upper - lower) / 2;
            }

            double pm = checkedCumulativeProbability(xm);

            if (pm >= p) {
                upper = xm;
            } else {
                lower = xm;
            }
        }

        return upper;
    }


    /**
     * {@inheritDoc}
     */
    @Override
    public void reseedRandomGenerator(long seed) {

        randomData.reSeed(seed);
    }


    /**
     * {@inheritDoc}
     * The default implementation uses the
     * <a href="http://en.wikipedia.org/wiki/Inverse_transform_sampling">
     * inversion method</a>.
     */
    @Override
    public int sample() {

        return randomData.nextInversionDeviate(this);
    }


    /**
     * {@inheritDoc}
     * The default implementation generates the sample by calling
     * {@link #sample()} in a loop.
     */
    @Override
    public int[] sample(int sampleSize) {

        if (sampleSize <= 0) {
            throw new NotStrictlyPositiveException(LocalizedFormats.NUMBER_OF_SAMPLES, sampleSize);
        }

        int[] out = new int[sampleSize];

        for (int i = 0; i < sampleSize; i++) {

            out[i] = sample();
        }

        return out;
    }


    /**
     * Computes the cumulative probability function and checks for {@code NaN}
     * values returned. Throws {@code MathInternalError} if the value is
     * {@code NaN}. Rethrows any exception encountered evaluating the cumulative
     * probability function. Throws {@code MathInternalError} if the cumulative
     * probability function returns {@code NaN}.
     *
     * @param argument input value
     * @return the cumulative probability
     * @throws MathInternalError if the cumulative probability is {@code NaN}
     */
    private double checkedCumulativeProbability(int argument) throws MathInternalError {

        double result = Double.NaN;

        result = cumulativeProbability(argument);

        if (Double.isNaN(result)) {

            throw new MathInternalError(
                LocalizedFormats.DISCRETE_CUMULATIVE_PROBABILITY_RETURNED_NAN, argument);
        }

        return result;
    }
}
